from knapsack import Knapsack
import numpy as np
class DP(Knapsack):
    def __init__(self, table, W):
        super(DP, self).__init__(table, W)
        
        #solution
        self.maxVals = 0
        self.k = self.n
        self.surCap = self.W#surplus capacity
    def dp(self, W, n):
        if n == 0 or W == 0:
            return 0
        if self.costs[n-1] > W:
            return self.dp(W,n-1)
        else:
            return max(self.dp(W-self.costs[n-1], n-1) + self.vals[n-1],self.dp(W, n-1))
    def run(self):
        self.maxVals = self.dp(self.W, self.n)
        return self.maxVals

table = np.loadtxt("table.csv", int)
print("#### DP algorithm to solve 0-1 knapsack problem ###")
print("******table********")
print(table)
print("*******************")


W = int(input("enter W: "))
K = DP(table, W)
print("W:",K.W, "n:", K.n)
print("costs:",K.costs)
print("vals:", K.vals)
K.run()
print("***solution of DP***")
print("maxval:",K.maxVals)
print("********************")
print("###################################################")
